package com.itheima.datastructure.heap;

import java.util.Arrays;
/*
小顶堆
 */
public class MinHeap {
    int [] array;
    int size;

    public MinHeap(int capacity){this.array=new int[capacity];}

    //是否满了
    public boolean isFull(){
        return size==array.length;
    }

    //获取堆顶元素
    public int peek(){
        return array[0];
    }

    //删除堆顶元素
    public int poll(){
        //记录堆顶元素
        int top=array[0];
        //将堆顶元素交换末尾元素
        swap(0,size-1);
        size--;
        //下潜调整
        down(0);
        return top;
    }

    //删除指定索引的元素
    public int poll(int index){
        int deleted=array[index];
        swap(index,size-1);
        size--;
        down(index);
        return deleted;
    }

    //替换堆顶元素
    public void replace(int replaced){
        array[0]=replaced;
        down(0);
    }

    //堆的尾部添加元素
    public boolean offer(int offered){
        if(size== array.length){
            return false;
        }
        up(offered);
        size++;
        return true;
    }

    //将添加元素上浮，直至offered大于父元素或者成为堆顶
    private void up(int offered){
        int child=size;
        while(child>0){
            int parent=(child-1)/2;
            if(offered<array[parent]){
                array[child]=array[parent];
            }else {
                break;
            }
            child=parent;
        }
        array[child]=offered;
    }
    public MinHeap(int [] array){
        this.array=array;
        this.size=array.length;
        heapify();
    }

    //建堆
    private void heapify(){
        //如何找到最后的非叶子节点 size/2-1;
        for(int i=size/2-1;i>=0;i--){
            //下潜操作
            down(i);
        }
    }
    //将parent索引处的元素下潜：与两个孩子比较，直至没有孩子比他大
    private void down(int parent){
        int left=parent*2+1;
        int right=left+1;
        int min=parent;
        if(left<size && array[left]<array[min]){
            min=left;
        }
        if(right<size && array[right]<array[min]){
            min=right;
        }
        if(min!=parent){
            swap(min,parent);
            //递归
            down(min);
        }
    }
    //交换两个索引处的元素
    private void swap(int i,int j){
        int t=array[i];
        array[i]=array[j];
        array[j]=t;
    }

}
